#include <math.h>
#include <set>
#include <iostream>

using std::cout;
using std::endl;
using std::set;
using std::ostream;
using std::multiset;

template <class Container>
void display(const Container & c)
{//形参使用了const关键字，则迭代器也必须要是const的
    typename Container::const_iterator it = c.begin();
    while(it != c.end()) {
        cout << *it << " ";
        ++it;
    }
    cout << endl;
}

class Point
{
public:
    Point(int ix = 0, int iy =0)
    : _ix(ix)
    , _iy(iy)
    {
        cout << "Point(int=0,int=0)" << endl;
    }

    Point(const Point & rhs)
    : _ix(rhs._ix)
    , _iy(rhs._iy)
    {
        cout << "Point(const Point & rhs)" << endl;
    }

    Point(Point && rhs)
    : _ix(std::move(rhs._ix))
    , _iy(std::move(rhs._iy))
    {
        cout << "Point(Point&&)" << endl;
    }
    
    friend ostream & operator<<(ostream & os, const Point & rhs);

    double getDistance() const
    {
        return sqrt(_ix * _ix + _iy * _iy);
    }

private:
    int _ix;
    int _iy;
};

ostream & operator<<(ostream & os, const Point & rhs)
{
    os << "(" << rhs._ix
       << "," << rhs._iy
       << ")";
    return os;
}

//重载了Point的小于符号
bool operator<(const Point & lhs, const Point & rhs)
{
    return lhs.getDistance() < rhs.getDistance();
}

void test0()
{
    cout << "test0()" << endl;
    //底层实现是红黑树
    set<int> numbers{3, 2, 1, 3, 2, 5, 5, 4, 6, 7, 8, 9, 8, 9};
    cout << "numbers:";
    display(numbers);

    //通过set的第二个模板参数，可以改变排序方式
    set<int, std::greater<int>> numbers2{3, 2, 1, 3, 2, 5, 5, 4, 6, 7, 8, 9, 8, 9};
    cout << "numbers2:";
    display(numbers2);

    //不能存放关键字相同的元素
    //Q:内部也没有重载等于符号，那set中如何判断两个元素相等的呢？
    //A:  !(x < y) && !(y < x)
    //      x >=y   &&  y >= x
    //   推导出  x 等于 y
    set<Point> points {
        {1,1},
        {2,2},
        {3,3},
        {4,4},
        {1,1}
    };
    display(points);
}

void test1()
{
    cout << "\ntest1()" << endl;
    multiset<int> numbers{3, 2, 1, 3, 2, 5, 5, 4, 6, 7, 8, 9, 8, 9};
    display(numbers);
    //查找等于5的第一个元素的位置(下限)
    auto it1 = numbers.lower_bound(5);
    //查找最后一个等于5的元素的下一个位置(上限)
    auto it2 = numbers.upper_bound(5);
    cout << "*it2:" << *it2 << endl;
    while(it1 != it2) {
        cout << "*it1:" << *it1 << endl;
        ++it1;
    }

    //直接获取关键字为8的下限和上限
    auto pret = numbers.equal_range(8);
    cout << *pret.first << endl;
    cout << *pret.second << endl;
    it1 = pret.first;
    while(it1 != pret.second) {
        cout << *it1 << " ";
        ++it1;
    }
    cout << endl;

}

int main()
{
    test0();
    test1();
    return 0;
}

